377. 组合总和 Ⅳ

Similar Question

Solution Tips

爬楼梯, 完全背包版本: 代码随想录

方案一: 完全背包问题 + 求排列方案数量

关键词就是调换两个 for 循环的顺序

但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。

如果本题要把排列都列出来的话，只能使用回溯算法爆搜

var combinationSum4 = function(nums, target) {
    // 完全背包问题 + 组合方式
    const n = nums.length;
    // 1. 在 总值为 j 时, 使用 [0-i] 面额的数字, 有多少种组合方式
    const dp = Array.from({ length: target + 1 }, () => 0);
    // 3. 在总值为 0 时, 不能选择任何数字, 只有 1 种方法
    dp[0] = 1;

    for (let j = 0; j <= target; j++) {
        for (let i = 0; i < n; i++) {
            // 2. 使用当前 num 后, 剩余的空间直接参考已有的方案总数为 dp[j - nums[i]]
            // 不使用当前硬币, 则方案数和之前的一样, 即: dp[j]
            if (j >= nums[i]) dp[j] += dp[j - nums[i]];
        }
        // console.log(dp.concat());
    }

    return dp[target];
};
let nums = [1,2,3], target = 4
console.log(combinationSum4(nums, target));